// https://leetcode.cn/problems/remove-k-digits/

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

// 算法思路总结：
// 1. 贪心策略维护单调非递减栈
// 2. 移除比当前数字大的前导数字
// 3. 处理剩余移除次数和前导零情况
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

class Solution 
{
public:
    string removeKdigits(string num, int k) 
    {
        int length = num.size();

        if (length == k) return "0";

        vector<char> stack;
        for (const char& digit : num)
        {
            while (k > 0 && !stack.empty() && stack.back() > digit)
            {
                stack.pop_back();
                k--;
            }
            stack.push_back(digit);
        }

        if (k > 0)
        {
            stack.resize(stack.size() - k);
        }

        int start = 0;
        while (start < stack.size() && stack[start] == '0')
        {
            start++;
        }

        if (start == stack.size()) return "0";

        return string(stack.begin() + start, stack.end());
    }
};

int main()
{
    string num1 = "1432219", num2 = "10200", num3 = "10";
    int k1 = 3 , k2 = 1, k3 = 2;

    Solution sol;

    cout << sol.removeKdigits(num1, k1) << endl;
    cout << sol.removeKdigits(num2, k2) << endl;
    cout << sol.removeKdigits(num3, k3) << endl;

    return 0;
}